package top.huhuiyu.ds.sort;

/**
 * 快速排序
 * 
 * @author Aiden Pearce
 *
 */
public class QuickSort {
  public static void sort(int[] array) {
    // 开始查找的数据是整个数组
    sort(array, 0, array.length-1);
  }

  public static void sort(int[] array, int start, int end) {
    // 递归要点，停止条件,查找的区间必须合法
    if (start > end) {
      return;
    }
    // 定义变量
    int i, j;
    // 基准数
    int base;
    // 交换位置的临时变量
    int temp;
    // 挑选基准数为第一个数
    base = array[start];
    // 初始化查找位置
    i = start;
    j = end;
    // 当i小于j的时候就会循环查找需要交换的值
    while (i < j) {
      // 右边开始找小于基准数的数所在位置
      while (base <= array[j] && i < j) {
        j--;
      }
      // 左边开始找大于基准数的数所在的位置
      while (base >= array[i] && i < j) {
        i++;
      }
      // 如果找到了合适的数就交换位置
      if (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
    // 将基准数放到i的位置(这个时候i前面的都比基准数小，后面的数大)
    array[start] = array[i];
    array[i] = base;
    // 递归必须是调用自己
    // 处理左半区
    sort(array, start, i - 1);
    // 处理右半区
    sort(array, i + 1, end);
  }
}
